package com.leetcode.字符串;

/**
 * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
 * <p>
 * 说明：本题中，我们将空字符串定义为有效的回文串。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: "A man, a plan, a canal: Panama"
 * 输出: true
 * 解释："amanaplanacanalpanama" 是回文串
 * 示例 2:
 * <p>
 * 输入: "race a car"
 * 输出: false
 * 解释："raceacar" 不是回文串
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 2 * 105
 * 字符串 s 由 ASCII 字符组成
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xah8k6/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 验证回文串 {

	/**
	 * 方法 1：双指针解决
	 * 就是使用双指针，一个指向前，一个指向后，遇到空格以及特殊字符要跳过
	 *
	 * @param s
	 * @return
	 */
	public static boolean isPalindrome1(String s) {
		char[] chars = s.toLowerCase().toCharArray();
		int length = chars.length;
		for (int i = 0, j = length - 1; i < j; i++, j--) {
			while (i < j && !Character.isLetterOrDigit(chars[i])) {
				i++;
			}
			while (i < j && !Character.isLetterOrDigit(chars[j])) {
				j--;
			}
			if (chars[i] != chars[j]) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 方法 2：双指针的另一种写法
	 *
	 * @param s
	 * @return
	 */
	public static boolean isPalindrome2(String s) {
		if (s.length() == 0) {
			return true;
		}
		int left = 0, right = s.length() - 1;
		while (left < right) {
			//因为题中说了，只考虑字母和数字，所以不是字母和数字的先过滤掉
			while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
				left++;
			}
			while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
				right--;
			}
			//然后把两个字符变为小写，在判断是否一样，如果不一样，直接返回false
			if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
				return false;
			}
			left++;
			right--;
		}
		return true;
	}

	/**
	 * 方法 3：使用正则匹配
	 *
	 * @param s
	 * @return
	 */
	public static boolean isPalindrome3(String s) {
		String actual = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
		String rev = new StringBuffer(actual).reverse().toString();
		return actual.equals(rev);
	}

	/**
	 * 方法 4：使用递归
	 *
	 * @param s
	 * @return
	 */
	public static boolean isPalindrome4(String s) {
		return isPalindromeHelper(s, 0, s.length() - 1);
	}

	public static boolean isPalindromeHelper(String s, int left, int right) {
		if (left >= right) {
			return true;
		}
		while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
			left++;
		}
		while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
			right--;
		}
		return Character.toLowerCase(s.charAt(left)) == Character.toLowerCase(s.charAt(right)) && isPalindromeHelper(s, ++left, --right);
	}


	public static void main(String[] args) {
		System.out.println(isPalindrome4("A man, a plan, a canal: Panama"));
	}
}
